#pragma once

#include <stack>
#include <utility>
#include <vector>

namespace solution_085
{

class Solution
{
public:
    int maximalRectangle(std::vector< std::vector<char> >& matrix)
    {
        if (matrix.empty() || matrix.front().empty())
            return 0;
        int max_rect = 0;

        std::vector<int> heights(matrix.front().size() + 1, 0);
        heights.back() = -1;
        for (int row = 0; row < (int)matrix.size(); ++row) {
            for (int col = 0; col < (int)matrix.front().size(); ++col) {
                if (matrix[row][col] == '1')
                    ++heights[col];
                else
                    heights[col] = 0;
            }

            std::stack<int> mono;
            mono.push(-1);
            for (int col = 0; col < (int)heights.size(); ++col) {
                while ( mono.top() >= 0 && heights.at(col) <= heights.at(mono.top()) ) {
                    int h = heights.at(mono.top());
                    mono.pop();

                    int w = col - mono.top() - 1;
                    max_rect = std::max(max_rect, w * h);
                }
                mono.push(col);
            }
        }

        return max_rect;
    }
};

}  /* namespace solution_085 */
